Introduction to Machine Learning

Unit 09: Bagging and Random Forest

1. Introduction

Single decision trees have high variance: flip a few training samples and the entire tree changes. This unit solves that problem architecturally. We begin with a geometric look at DT decision boundaries (axis-aligned rectangles), then introduce bootstrap resampling. We cover ensemble learning in two flavors: parallel Bagging (Bootstrap Aggregating) and sequential Boosting. We then introduce Random Forest and its even more randomized cousin, Extremely Randomized Trees (ExtraTrees).

Learning Objectives

2. Theory

2.1 Bootstrapping — Create Many Datasets From One

Problem: we want to train 500 diverse trees, but we only have one training dataset of size \(n\). Bootstrapping solves this by drawing \(n\) samples with replacement to form a synthetic "bootstrap replicate" dataset, also of size \(n\).

Bootstrap sampling and out-of-bag validation An original dataset of six samples generates bootstrap replicates through sampling with replacement. Approximately 63.2 percent of unique observations are included and 36.8 percent remain out-of-bag. Bootstrap sampling Sampling with replacement creates independent replicates — and a built-in validation set. ORIGINAL DATASET n = 6 samples: [a, b, c, d, e, f] Each replicate contains 6 draws BOOTSTRAP SAMPLE #1 [a, a, c, d, f, f] a and f drawn twice b and e left out BOOTSTRAP SAMPLE #2 [b, b, b, d, e, f] b drawn three times a and c missing BOOTSTRAP SAMPLE #3 [a, c, c, d, e, e] c and e drawn twice b and f left out Why this matters On average, each bootstrap replicate contains approximately 63.2% unique data points 36.8% out-of-bag (OOB) The OOB observations form a free validation set without requiring a separate holdout dataset. EXPECTED FRACTIONS · LARGE n OOB = (1 − 1/n)ⁿ → 1/e ≈ 36.8% Unique = 1 − (1 − 1/n)ⁿ ≈ 63.2% Each item has a chance to be selected on every draw. Sampling with replacement • Repeated observations are expected • OOB data remains unused by that replicate

2.2 Ensemble Learning Taxonomy

PropertyBagging (e.g., Random Forest)Boosting (e.g., AdaBoost, Gradient Boosting)
Execution✅ Parallel — every base learner trained independently🔁 Sequential — model t+1 depends on model t's residuals
GoalReduce variance by averagingReduce bias by reweighting hard samples
Base LearnerDeep/high-variance (unlimited-depth trees)Shallow/low-variance (stumps, depth=1..6)
Weight schemeUniform average (or weighted average)Each model weighted by its accuracy (AdaBoost)
OverfittingMore trees ⇒ never really hurts; convergence OOBToo many rounds ⇒ overfits (need early stop)

2.3 Bagging (Bootstrap Aggregating)

Given a base learner \(h\) and \(B\) bootstrap samples: train \(h_b = h(\text{bootstrap-sample-}b)\) for \(b=1..B\). Aggregate by unweighted average (regression) or majority vote (classification):

\[ \hat{f}_{\text{bag}}(x) = \frac{1}{B}\sum_{b=1}^{B} h_b(x) \quad \text{(regression)}, \qquad \hat{y}_{\text{bag}}(x) = \text{maj-vote}\left(\{h_b(x)\}_{b=1}^{B}\right) \quad \text{(class)} \]

2.4 Random Forest — Bagging + Random Feature Subsets

Bagging alone doesn't fully de-correlate trees because they all share the same dominant root split. Random Forest (Breiman, 2001) injects a second source of randomness: at every node of every tree, choose the best split from a random subset of \(m_{\text{try}}\) features, not all \(d\) of them. This decorrelates trees dramatically.

RF HyperparameterDefault Rule of ThumbEffect
n_estimators = \(B\)100…500 (as many as you can afford)More trees → smoother, more stable. No overfit from too many!
max_features = \(m_{\text{try}}\)Classification: sqrt(d); Regression: d/3Small → more de-correlation; too small → underfit.
max_depthNone (grow fully) — RF variance-averaging handles itDepth limits only help at small B or for speed.
min_samples_leaf1Increasing smooths boundaries.

2.5 Out-of-Bag (OOB) Validation — Free Cross-Validation

For each training sample \((x_i, y_i)\), roughly 36.8% of trees never saw it during bootstrap training. Use those trees as a validation panel for sample \(i\): average their predictions → OOB prediction. The full-dataset OOB error is an approximately unbiased estimate of test error — no data wasted!

📌 OOB Usage Recipe

  1. Set oob_score=True in scikit-learn's RandomForestClassifier.
  2. Train on 100 % of training data (no separate validation split needed).
  3. Read model.oob_score_ for an unbiased held-out accuracy estimate.
  4. Use this to tune max_features, n_estimators, min_samples_leaf, etc.

2.6 Extremely Randomized Trees (ExtraTrees)

RF still uses the optimal split threshold for each of the \(m_{\text{try}}\) candidate features. ExtraTrees (Geurts et al., 2006) goes one step further: for each candidate feature, it samples the split threshold uniformly at random from that feature's range, then picks the best of those random splits. ExtraTrees is:

3. Interactive Examples

Example 1: Hand Bootstrap — n = 7

Original dataset samples indexed \(\{1,2,3,4,5,6,7\}\). Using a random-number table, one bootstrap replicate draws indices: [3, 1, 3, 7, 5, 1, 4].

(a) Which original samples are in-bag? Which are OOB?

In-bag (unique): {1, 3, 4, 5, 7} (5/7 ≈ 71.4%).
OOB: {2, 6} — samples never drawn (2/7 ≈ 28.6% ≈ close to 36.8% theoretical for large n).

(b) What is the count (not unique) of each in-bag index in that replicate?

1→2×, 3→2×, 4→1×, 5→1×, 7→1×. (With-replacement sampling naturally produces weights on each in-bag sample.)

Example 2: Majority-Vote Ensemble

5 independent binary classifiers vote on a sample. Their predictions: \(h_1 = +1,\; h_2 = -1,\; h_3 = -1,\; h_4 = +1,\; h_5 = +1\).

What does majority-vote Bagging output? If the true label is +1, how many individual classifiers are wrong? Is the ensemble right?

Votes: +1 × 3, −1 × 2 → ensemble prediction = +1 (correct). h₂ and h₃ are wrong (2/5 = 40 % individual error). Majority-vote ensemble wins despite many weak voters — the core wisdom-of-crowds mechanism!

Example 3: RF max_features Intuition

Binary classification, d = 100 features, n_estimators = 300.

(a) What's the default RF max_features per split? (b) If we set max_features = 1.0 (full d), what method do we recover? (c) If we set it to 1, what happens?

(a) Classification default = ⌊√d⌋ = 10 features per split.
(b) max_features=d = pure Bagging (no feature randomness). Worse de-correlation.
(c) max_features=1 = each split picks one random feature then thresholds it. Extremely aggressive de-correlation at the cost of bias — rarely optimal in practice.

4. Numerical Solutions

Problem 1: Expected OOB Size (Asymptotic)

For very large \(n\), what is the approximate fraction of unique training samples used in any one bootstrap replicate?

📘 Step-by-Step Derivation

Step 1: Probability a specific sample \(i\) is NOT drawn in one draw = \(1 - 1/n\).

Step 2: Over \(n\) independent draws, P(i never drawn) = \((1 - 1/n)^n\).

Step 3: Limit: \(\lim_{n\to\infty}(1-1/n)^n = 1/e \approx 0.3679\).

Step 4: P(i in bag) = \(1 - 1/e \approx 63.2\%\). Each replicate uses ~63.2 % of the unique original samples — matches the hand-n=7 example closely!

Problem 2: RF Probability via Tree Votes

A Random Forest with B = 100 trees classifies a loan applicant. 72 trees vote DEFAULT; 28 vote NOT-DEFAULT.

📘 Step-by-Step — Prediction, Probability, and (Un)certainty

Step 1 (Class): Majority vote = DEFAULT (72 > 28).

Step 2 (Prob): RF class probability = fraction of trees voting for class = P̂(DEFAULT) = 0.72.

Step 3 (Uncertainty): 72/28 is a strong vote (> 2:1 ratio) → confident prediction. Compare with a 51/49 vote, which would be near the decision boundary and could benefit from more trees.

Problem 3: Why RF Feature Importances Are More Stable Than Single DT

Two highly correlated features Age and Tenure both predict churn. Compare single-depth-8 DT vs. RF (B=500, m=√d) in terms of how importances are distributed.

📘 Explanation
  • Single DT: Greedy pick at root selects whichever feature happens to win on this training set (random tie-break). Feature importances will be ~90% on one, ~10% on the other. A different bootstrap sample would flip the ratio.
  • Random Forest: Because of feature subsampling at each split, ~50 % of splits will have only Age in the candidate set, ~50 % only Tenure. The two features share the credit across 500 trees, giving importances near 50/50. RF importances are far more stable and trustworthy.

5. Try It Yourself

Problem 1 — Bootstrap Replicate (n=5)

Dataset S = {P, Q, R, S, T}. A bootstrap draw yields: [S, S, P, R, P].

  1. List the in-bag unique samples and the OOB samples.
  2. Compute the empirical in-bag fraction and compare to asymptotic 63.2 %.
  1. In-bag unique = {P, R, S}; OOB = {Q, T}.
  2. In-bag = 3/5 = 60 % (close to 63.2 % for n=5 small).
Problem 2 — Weighted (AdaBoost-Style) Vote

Three weak learners have accuracies α₁ = 0.9, α₂ = 0.6, α₃ = 0.6. (α = the log-odds weight used in AdaBoost is ln((1-ε)/ε).)

Compute the signed weight w = 2α − 1 for each, then output the final weighted-vote sign of (−1, +1, +1) predictions.

w₁ = 0.8, w₂ = 0.2, w₃ = 0.2. Sum = 0.8·(−1) + 0.2·(+1) + 0.2·(+1) = −0.8 + 0.4 = −0.4. Sign is negative → final prediction = −1 (class 0 / minority class). The strong classifier (α₁=0.9) overruled two weak ones.
Problem 3 — OOB vs. Holdout Sizing

n_train = 10,000. Compare: (a) 5-fold CV (train size per fold), (b) size of the OOB panel for any single tree in RF (approx), (c) size of the OOB prediction set for the whole RF (all training points have an OOB panel).

(a) 5-fold CV: each fold uses 8,000 for training, 2,000 for validation.
(b) For one tree, OOB ≈ 36.8 % × 10,000 ≈ 3,680 samples.
(c) For the whole RF, every one of the 10,000 training points has an OOB prediction (it's averaged over its specific ~36.8 % of OOB trees) — so full 10,000-point validation set, no data lost to a holdout.

6. Interactive Quiz

Answer all 5 MCQs. Click on an option to get instant feedback.

Your score: 0 / 5

7. Key Takeaways

  1. Single DTs carve the feature space into axis-aligned rectangles. Easy to plot but brittle (high variance). Swap a few training samples → big boundary changes.
  2. Bootstrap = draw n samples with replacement. Asymptotically, each replicate uses ~63.2 % of unique original training points. The other ~36.8 % are Out-of-Bag (OOB) — a free validation set.
  3. Two ensemble paradigms: Bagging (parallel, independent high-variance base learners, average/vote → reduces variance); Boosting (sequential, reweight hard samples or fit residuals → reduces bias).
  4. Random Forest = Bagging + random feature subsets at every split. Defaults: B ∈ [100..500], m_try = ⌊√d⌋. The extra randomness de-correlates trees, which is what makes averaging work dramatically well.
  5. OOB score is your best friend. Set oob_score=True and use the ~unbiased OOB accuracy to tune hyperparameters — no need to waste a validation split on medium/large data.
  6. ExtraTrees = RF + random thresholds per candidate feature. Faster to train, often matches RF accuracy, and complements RF in a stacked ensemble.

8. Common Pitfalls

  1. Using "n_estimators too low" (B=10) and calling it "Random Forest." RF only beats single DT at B large enough for averaging to kick in. Start at B=100 minimum.
  2. Setting max_features = d (all features) in RF. You recover plain Bagging, losing the decorrelation benefit. Use sqrt(d) for classification, d/3 for regression.
  3. Forgetting to shuffle / class-stratify when bagging on imbalanced data. Bootstrap replicates from a 99/1 dataset are often ~99/1 themselves! Use class_weight='balanced_subsample' in scikit-learn.
  4. Using OOB predictions for hyperparameter tuning on tiny (n < 500) datasets. OOB has higher variance at small n — stick to stratified 5-fold CV instead.
  5. Comparing RF (n=500) against a single DT (n_estimators=1) on speed and concluding "RF is slow." Compare apples to apples: accuracy at fixed compute budget. RF nearly always wins that comparison.
  6. Deep-pruning max_depth in RF "to prevent overfit." RF's averaging already handles variance! Leave depth unlimited (the default) and tune m_try and/or n_estimators first.